package LeetCode._01算法入门.day11递归回溯;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @author 挚爱之夕
 * @date 2022-03-02 - 03 - 02 - 12:47
 * @Description 给定一个不含重复数字的数组nums，
 * 返回其所有可能的全排列，你可以按任意顺序返回答案。
 * @Version 中等
 */
public class _46全排列 {
    static int[] nums = {1, 2, 3};
    @Test
    public void solve(){
        List<List<Integer>> res = permute(nums);
        System.out.println(res);
    }
    public List<List<Integer>> permute(int[] nums) {
        //结果
        List<List<Integer>> res = new ArrayList<>();

        //初始化为原顺序
        List<Integer> output = new ArrayList<>();
        for (int num : nums) {
            output.add(num);
        }

        int n = nums.length;
        //构造全排列
        backtrack(n, output, res, 0);
        return res;
    }

    /**
     * 构造全排列
     * @param n 元素个数
     * @param output 一个排列（最初顺序）
     * @param res 排列的所有情况
     * @param first 开始下标
     */
    public void backtrack(int n, List<Integer> output, List<List<Integer>> res, int first) {
        // 所有数都填完了
        if (first == n) {
            res.add(new ArrayList<>(output));
            return; //有无此语句都可，下面的循环都不执行
        }

        for (int i = first; i < n; i++) {
            // 动态维护数组
            Collections.swap(output, first, i);
            // 继续递归填下一个数
            backtrack(n, output, res, first + 1);
            // 撤销操作
            Collections.swap(output, first, i);
        }
    }
}
